package teach.sort;

import java.util.Arrays;

public class QuickSort2 {
    public static void main(String[] args) {
        //int[] arr = {8, 1, 4, 9, 0, 3, 5, 2, 7, 6};
        int[] arr = {6, 4, 9, 1, 7, 2, 5, 8};
        System.out.println(Arrays.toString(arr));
        sort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr,int start,int end){
        int pivot = arr[end];

        int x = start;
        int y = end;

        while(x<y){
            while(x<y && arr[y]>pivot){
                y--;
            }
            while(x<y && arr[x]<pivot){
                x++;
            }
            if(x<y && arr[x] == arr[y]){
                x++;
            }else{
                int temp = arr[y];
                arr[y] = arr[x];
                arr[x] = temp;
            }
        }
        if(x-1>start){
            sort(arr,start,x-1);
        }
        if(y+1<end){
            sort(arr,y+1,end);
        }
    }
}
